package org.misty.practices.algorithm.step;

/*
有N级台阶，每次可以走1步或2步，共有多少种走法

n=1    1步                    f(1)=1
n=2    一次1步或直接2步         f(2)=2
n=3    先到达f(1)，然后跨2步    f(3)=f(1)+f(2)
       先到达f(2)，然后跨1步
n=4    先到达f(2)，然后跨2步    f(4)=f(2)+f(3)
       先到达f(3)，然后跨1步
...
n=x    先到达f(x-2)，然后跨2步   f(x)=f(x-2)+f(x-1)
       先到达f(x-1)，然后跨1步
 */

/**
 * @author Misty on 2020-06-02
 */
public class StepsRecur {

    public static int step(int n) {
        if (n == 1 || n == 2) return n;
        return step(n - 2) + step(n - 1);
    }

    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        System.out.println(step(45));
        long e = System.currentTimeMillis();
        System.out.println(e - s);
    }
}
